class Solution:
    def largestRectangleArea(self, heights: list) -> int:
        # if len(heights) == 0:
        #     return 0
        # up_zhan, res = [[0, 0], ], min(heights) * len(heights)
        up_zhan, res = [[0, 0], ], 0
        heights.append(0)
        for index, num in enumerate(heights):
            while num < up_zhan[-1][1]:
                mid_num = up_zhan.pop(-1)
                res = max(res, mid_num[1] * (index - up_zhan[-1][0]))
            up_zhan.append([index+1, num])
        return res


a = Solution()
print(a.largestRectangleArea([2, 1, 5, 6, 2, 3]))
print(a.largestRectangleArea([2]))
print(a.largestRectangleArea([]))
print(a.largestRectangleArea([2, 1, 2]))
print(a.largestRectangleArea([3, 2, 3]))
print(a.largestRectangleArea([5, 4, 1, 2]))
